1. Field of the Invention
This invention relates to computer network technology, and more particularly, to a data item interval identifier lookup method and system which is designed for integration to a data processing system (such as a computer unit, a network server, or a network system), for providing an interval identifier lookup function to an input data item (such as an IP address, a memory address, or a hard disk address), for finding where in a number of predefined intervals the value of the input data item belongs.
2. Description of Related Art
In the field of computer data processing, there exists a need for techniques that can process a fixed-length numerical data item, such as an IP address, a memory address, or a hard disk address, in such a manner as to find where in a number of predefined intervals the value of the input data item belongs. This allows different actions to be performed on the input data item based on its fitted interval.
In the field of computer networking, packet classification is an important mechanism that is used to determine the type of each packet that is being received and transmitted over a network system, such as the Internet, so that different operations can be performed for different types of packets. For example, the entire value range of the packet's destination IP address format can be divided into a number of intervals, with each interval being assigned to a unique identifier and corresponding to a different packet handling method. This allows a packet to be classified based on which interval the value of its destination IP address belongs.
Presently, the aforementioned interval identifier lookup function for IP addresses can be implemented with a one-stage lookup table, which maps the entire IP address value range to predefined intervals (each interval being represented by a numerical identifier), so that the value of an input IP address is directly used as an index for retrieving the corresponding interval identifier from the lookup table. One drawback to this conventional method, however, is that the one-stage lookup table requires the use of a memory space for storage that is exponentially proportional to the entire value range of the IP address; i.e., if the IP address has a length of L bits, then the required memory space for storing the lookup table is proportional to 2L. For example, in the case of IPv4 compliant IP address format which has a length of 32 bits, the total data amount for implementing the lookup table is proportional to 232. In the case of IPv6 compliant IP address format which has a length of 128 bits, the total data amount is proportional to 2128. As a result, the one-stage lookup table method would require a huge amount of memory space for implementation. This drawback causes the implementation of packet classification to have low system performance.
In view of the above-mentioned drawbacks of the prior art, it is a research effort in the information technology industry for a new and improved IP address interval identifier lookup technique which can be implemented with low memory requirement and high system performance.